Địa danh An Phú Đông có từ thời Pháp thuộc, khi đó là tên một làng thuộc tổng Bình Trị Thượng, quận Gò Vấp, tỉnh Gia Định. Làng An Phú Đông được hình thành trên cơ sở sáp nhập hai làng có từ thời Nguyễn là An Lộc Đông và Hanh Phú.

Sau năm 1956, các làng được gọi là xã, An Phú Đông là một xã thuộc quận Gò Vấp.

Sau năm 1975, xã An Phú Đông được sáp nhập vào huyện Hóc Môn, Thành phố Hồ Chí Minh.

Ngày 6 tháng 1 năm 1997, Chính phủ ban hành Nghị định số 03-CP[1]. Theo đó, chuyển xã An Phú Đông về Quận 12 mới thành lập và thành lập phường An Phú Đông trên cơ sở toàn bộ 856 ha diện tích tự nhiên, 7.749 người của xã An Phú Đông.